/*
    给定一个数组和一个目标值，在数组中找到目标值，并返回其索引。
    如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 */


package com.diudiu.BinarySearch;

public class Test02 {
    public static void main(String[] args) {
        //定义一个整数数组
        int[] array = {1, 3, 5, 6, 8, 10};
        //调用myBinarySearch方法，传入数组和目标值，返回目标值应该插入的位置
        int index = myBinarySearch(array, 11);
        System.out.println("目标值7应该插入的位置是：" + index);
    }

    //定义一个方法，用于二分查找
    private static int myBinarySearch(int[] array, int target) {
        //定义左指针
        int left = 0;
        //定义右指针
        int right = array.length - 1;
        //当左指针小于等于右指针时，循环
        while (left <= right) {
            //计算中间指针
            int mid = (left + right) >>> 1;
            //如果目标值小于数组的中间值，右指针等于中间指针减一
            if (target < array[mid]) {
                right = mid - 1;
                //如果目标值大于数组的中间值，左指针等于中间指针加一
            } else {
                left = mid + 1;
            }
        }
        //返回左指针
        return left;
    }
}
